DAY 16 試題

問題描述

給定一個單向鏈結串列的頭節點 head，以及一個整數 n，要求從該鏈結串列中移除倒數第 n 個節點，並返回修改後的鏈結串列的頭節點。

• 節點的數量 sz 為 1 到 30 之間。
• 每個節點的值範圍是 0 到 100 之間。
• n 的範圍是 1 到 sz 之間，保證有效。

例如：

1.

• 輸入：head = [1,2,3,4,5]，n = 2
• 輸出：[1,2,3,5]
• 解釋：移除倒數第 2 個節點後，結果為 [1,2,3,5]。

2.

• 輸入：head = [1]，n = 1
• 輸出：[]
• 解釋：鏈結串列中只有一個節點，移除後鏈結串列為空。

解題思路

要解決這個問題，可以採用雙指針法（Two Pointer Technique）。具體步驟如下：

1. 使用雙指針： 設置兩個指針 first 和 second，起始時都指向鏈結串列的頭節點。首先，讓 first 指針先向前移動 n 步。此時，second 指針仍然在起始位置。
2. 同步移動指針： 接著，同時移動 first 和 second 指針，直到 first 到達鏈結串列的尾端。此時，second 則指向要刪除節點的前一個節點。
3. 刪除節點： 當 first 到達尾端時，second 的下一個節點就是要刪除的節點，因此將 second 的 next 指向 second.next.next，從而移除該節點。
4. 處理特殊情況： 若刪除的是頭節點，只需要直接返回 head.next。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* first = dummy;
        ListNode* second = dummy;
        
        // 先移動 first 指針 n 步
        for (int i = 0; i <= n; ++i) {
            first = first->next;
        }
        
        // 同步移動 first 和 second
        while (first != nullptr) {
            first = first->next;
            second = second->next;
        }
        
        // 刪除倒數第 n 個節點
        second->next = second->next->next;
        
        // 返回頭節點
        return dummy->next;
    }
};

解法重點與分析

這個解法的核心在於利用雙指針技術，在一次遍歷中找到倒數第 n 個節點，並將其刪除。這樣的方法可以避免需要先計算整個鏈結串列的長度，從而提升效率。

1. 雙指針法的運用： 一個指針先走 n 步，然後兩個指針同時向前走，當第一個指針到達尾端時，第二個指針正好到達要刪除的節點前一個位置。
2. 虛擬頭節點： 為了簡化操作，特別是在要刪除頭節點的情況下，引入一個虛擬的頭節點 dummy，使得操作更加方便。
3. 時間與空間複雜度：

• 時間複雜度： 這個解法只需遍歷鏈結串列一次，時間複雜度為 O(sz)，其中 sz 是鏈結串列的節點數。
• 空間複雜度： 由於只使用了常數的額外空間，因此空間複雜度為 O(1)。

總結

通過雙指針技術，可以在一次遍歷中有效地找到並刪除倒數第 n 個節點。這種方法具有較高的效率，時間複雜度為 O(sz)，且空間複雜度為 O(1)，因此是一種簡潔且高效的解法。在實際編程中，引入虛擬頭節點可以有效避免處理頭節點刪除的特殊情況，使程式碼更加簡潔直觀。

以上是第十六天的自學內容分享，謝謝大家。